package 左哥算法.ch03堆;

import org.junit.Test;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 完全二叉树：即二叉树的倒数第二层必须为必须全部不为空，最后一层必须是从左到右连续的
 * 完全二叉树可以用数组表示，其节点与下标关系为：
 *  左子节点=i*2+1
 *  右子节点=i*2+2
 *  父节点=(i-1)/2
 *
 * 大根堆：所有父节点要比其子节点大
 */
public class Ch03堆排序 {

    /**
     * 大根堆插入测试
     */
    @Test
    public void test01(){
//        PriorityQueue
        int[] arr={2,1,3,4,5};
//        int[] arr={2,1,3,4,5,7,5,9,6};
        int heapSize=0;
        for (int i = 0; i <arr.length; i++) {   //对数组中所有元素进行插入
            heapInsert(arr,heapSize++);
        }
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 大根堆的插入
     * @param arr
     * @param index:可以从指定位置进行插入
     */
    public void heapInsert(int[] arr,int index){
        while (arr[index]>arr[(index-1)/2]){    //只有当新插入的节点比其父节点大时才替换
            replace(arr,index,(index-1)/2);     //和其父节点互换
            index=(index-1)/2;          //移到父节点的位置
        }
    }

    /**
     * 大根堆移除测试
     */
    @Test
    public void test02(){
//        int[] arr={5, 4, 2, 1, 3};
        int[] arr={9, 7, 5, 6, 3, 2, 5, 1, 4};
        int heapSize=arr.length;
        replace(arr,0,--heapSize);
        heapify(arr,0,heapSize);
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 移除大根堆的根节点
     * @param arr
     * @param index:可以从指定位置移除
     * @param size：堆的总长度
     */
    public void heapify(int[] arr,int index,int size){
//        replace(arr,index,--size);  //size是个数，不是末尾下标
        int left=index*2+1;
        while (left<size){
            int sonMax=left+1<size&&arr[left+1]>arr[left]?     //找出最大的子节点
                    left+1:left;
            int target=arr[sonMax]>arr[index]?sonMax:index;     //对比原节点与其子节点
            if (target==index){ //如果当原节点就是最大，则完成下放
                return;
            }
            replace(arr,index,target);
            index=target;   //将当前节点移到下一层
            left=index*2+1;
        }
    }

    @Test
    public void testHeapSort(){
        int[] nums={2,1,3,4,5,7,5,9,6};
        heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }
    /**
     * 堆排序：先将数组构建为大根堆
     * 再依次移走(heapify)堆中的根节点（即每次拿走最大的数）//可以将移除的元素放到数组最后，从而不用产生新的数组
     */
    public void heapSort(int[] nums){
        int heapSize=0;
//        while (heapSize<nums.length){   //构建堆
//            heapInsert(nums,heapSize++);
//        }
        for(int i=nums.length-1;i>=0;i--){
            heapify(nums,i,nums.length);
        }
        heapSize=nums.length;
        while (heapSize>0){             //依次移除堆
            replace(nums,0,--heapSize);
            heapify(nums,0,heapSize);
        }
    }

    public void replace(int[] arr,int a,int b){
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
}
